﻿////////////////////课程表系列1与2：
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

例如，先修课程对[0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。



示例 1：

输入：numCourses = 2, prerequisites = [[1, 0]]
    输出：true
        解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
        示例 2：

        输入：numCourses = 2, prerequisites = [[1, 0], [0, 1]]
        输出：false
        解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

        class Solution {
        public:
            //////////////////拓扑排序：
            bool canFinish(int n, vector<vector<int>>& p) {
                vector<int>rd(n);
                unordered_map<int, vector<int>>adlist;
                //准备工作：邻接表+入度表：
                for (auto a : p) {
                    adlist[a[1]].push_back(a[0]);
                    rd[a[0]]++;
                }
                //把一开始入度为0推入队列并启动：
                queue<int>q;
                for (int i = 0; i < n; i++) if (!rd[i])q.push(i);
                while (q.size()) {
                    //取出队列中元素（入度都是0的）
                    int course = q.front();
                    q.pop();
                    //把与它连的线即v点的入度--（发现减后为0再推入）
                    for (auto a : adlist[course]) {
                        if (!--rd[a]) q.push(a);
                    }
                }
                //如果有环也就意味着操作完后入度表中存在不为0的点（如果加入排序队列也可以看是否和原来所有点个数相等）
                for (auto a : rd) if (a)return false;
                return true;
            }
    };




    现在总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。

        给定一个数组 prerequisites ，它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。 例如 prerequisites[i] = [ai, bi] 表示想要学习课程 ai ，需要先完成课程 bi 。

        请根据给出的总课程数  numCourses 和表示先修顺序的 prerequisites 得出一个可行的修课序列。

        可能会有多个正确的顺序，只要任意返回一种就可以了。如果不可能完成所有课程，返回一个空数组。



        示例 1：

        输入 : numCourses = 2, prerequisites = [[1, 0]]
        输出 : [0, 1]
            解释 : 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为[0, 1]。
            示例 2：

            输入 : numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
            输出 : [0, 1, 2, 3] or [0, 2, 1, 3]
            解释 : 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此，一个正确的课程顺序是[0, 1, 2, 3]。另一个正确的排序是[0, 2, 1, 3]。



            class Solution {
            public:
                //////////////////拓扑排序：
                vector<int> findOrder(int n, vector<vector<int>>& p) {
                    vector<int> rd(n);
                    unordered_map<int, vector<int>> adlist;
                    vector<int>ret;
                    // 准备工作：邻接表+入度表：
                    for (auto a : p) {
                        adlist[a[1]].push_back(a[0]);
                        rd[a[0]]++;
                    }
                    //把一开始入度为0推入队列并启动：
                    queue<int> q;
                    for (int i = 0; i < n; i++) if (!rd[i])  q.push(i);
                    while (q.size()) {
                        int course = q.front();
                        q.pop();
                        ret.push_back(course);//进入排序好数组
                        //把与它连的线即v点的入度--（发现减后为0再推入）
                        for (auto a : adlist[course]) {
                            if (!--rd[a])  q.push(a);
                        }
                    }
                    for (auto a : rd) if (a) return vector<int>();//如果还存在数就说明有环
                    return ret;
                }

        };


